/*
 * @lc app=leetcode.cn id=402 lang=javascript
 *
 * [402] 移掉K位数字
 */

// @lc code=start
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */

// 错误
var removeKdigits1 = function (num, k) {
    if (num.length <= k) return '0'
    let stack = [0], ans = [], i = 1, count = 0
    while (stack.length > 0 && i < num.length) {
        let p = stack[stack.length - 1]
        if (num[i] <= num[p]) {
            stack.pop()
            ans.push(p)
            count++
            while (stack.length > 0 && count < k) {
                let p = stack[stack.length - 1]
                if (num[i] > num[p]) break
                else {
                    ans.push(stack.pop())
                    count++
                }
            }
        }

        if (num[i] == 0 && stack.length == 0)
            ans.push(i++)
        else
            stack.push(i++)

        if (count == k) break
    }
    let str = "", j = 0
    ans.sort((a, b) => a - b)
    for (let n of ans) {
        str += num.substring(j, n)
        j = n + 1
    }
    str += num.substring(j)
    return str == "" ? "0" : str
};

// 贪心算法
// 若要使得剩下的数字最小，需要保证靠前的数字尽可能小
var removeKdigits = function (num, k) {
    if (num.length <= k) return "0"
    let stack = [], count = k
    for (let n of num) {
        while (count > 0 && stack.length > 0 && stack[stack.length - 1] > n) {
            stack.pop()
            count--
        }
        stack.push(n)
    }
    while (count-- > 0) stack.pop()
    while(stack.length > 0 && stack[0] === '0') stack.shift()
    return stack.length > 0 ? stack.join('') : '0'
};
// @lc code=end

removeKdigits("1432219", 3)
